A path-compressed digital search trie (DST) that supports branching decisions based on single binary digits is often referred to as a Patricia trie. FIG. 1A illustrates a conventional digital search trie 10a that supports eight 8-bit search keys A-H and FIG. 1B illustrates a conventional Patricia trie 10b that is achieved by removing all unary branches from the trie 10a and labeling all remaining nodes with the distinguishing bit positions from the search keys A-H. Conventional search techniques include using selected bits from an applied search key to traverse the trie 10b and locate a result by a process of elimination.
FIGS. 2A-2B illustrate conventional multiple steps used to construct a Patricia trie 20 that supports N=8 keys of size W=16-bits. These eight keys are illustrated in the top left corner of FIG. 2A. In step 1, the leftmost bit (bit 15) is identified as a bit that can split the set of eight keys into two groups. The first group includes a single key (key 7), which has a leftmost bit equal to 1, and the second group includes the seven remaining keys having leftmost bits equal to 0. In step 2, the seven keys in the second group can be further split into a group of six keys and a group of one key based on the 12th bit. In step 3, the group of six keys identified in step 2 can be split into a group of two keys and a group of four keys based on the 10th bit. In step 4, the group of two keys identified in step 3 can be further split into two groups of one key each (keys 4 and 5), based on the 9th bit. In step 5, the group of four keys identified in step 3 can be split into a group of one key and a group of three keys based on the 8th bit. In step 6, the group of three keys identified in step 5 can be split into a group of two keys and a group of one key based on the 6th bit. Finally, in step 7, the group of two keys identified in step 6 is evenly split based on the 3rd bit. Thus, as illustrated by FIG. 2B, the nodes of the Patricia trie are labeled with the distinguishing bit positions (e.g., bits 15, 12, 10, 9, 8, 6 and 3). In particular, the trie 20 consists of nodes that identify a set of bit positions that are examined in an applied search key, and left and right branches (pointers) to follow based on the value of each examined bit.
As will be understood by those skilled in the art, the construction of the trie 20 requires log2W bits to encode each bit position, log2N bits to encode each of the left or right pointers and a bit to indicate whether a branch leads to another intermediate node or a leaf node. There are always N−1 branch nodes in a trie with N keys. Moreover, for N<W, all N−1 nodes must be visited in the worst case (skewed). For N>W, the number of nodes traversed is bounded by W (i.e., examine all bits in an applied key). In the best case, which occurs when the search trie is balanced, only log2N nodes are visited.
Searching the Patricia trie 20 of FIG. 2B using distinguishing bit values extracted from the applied search key results in the identification of a candidate key in a leaf node (or possibly pointed to by the leaf node) that may (or may not) exactly match the applied search key. To determine whether an exact match is present, the candidate key must be compared to the applied search key. For example, searching the trie 20 with an applied search key equal to 0001000111000000 will terminate at the leaf node containing key 6, which represents an exact match. However, searching the same trie 20 with a key equal to 0111111000111111 will also terminate at the leaf node containing key 6, but this key clearly does not match the applied search key.
In order to modify the trie 20 with the insertion of a new key, it is necessary to find a predecessor key (i.e., a key in the trie with the highest ordinal value less than the new key) or a successor key (i.e., a key in the trie with the lowest ordinal value greater than the new key). This may be accomplished by finding where a distinguishing bit is missing that would have led to the new key had the new key been present in the trie. One conventional technique to find the distinguishing bit includes finding a longest common prefix (LCP) between the new key (S) and a candidate key (K) and adjusting all bits following the LCP. A new pseudo-key P may be created consisting of the concatenation of the LCP and a string of all 0's or 1's, depending on whether the bit following the LOP in the new key is a 0 or 1. For example, if the new key (S) equals 0110100011000001, then a search of the trie 20 results in an identification of key 2 (0000001001100011) as the candidate key, which does not equal to the new key. The LOP between the new key and the candidate key (key 2) is LCP=0***************. This LCP value indicates that the first distinguishing bit should have been bit 14 of the new key S, which equals 1. The pseudo-key is therefore P=0111111111111111. Performing a search of the trie 20 using the pseudo-key P results in an identification of key 6. Because bit 14 of the new key S is 1, key 6 must be a predecessor of the new key S. This confirms the following relationship: key 6<new key S<key 7. Based on this relationship, the new key S is identified as key 7 and original key 7 is renumbered as key 8 in the conventional trie 20′ in FIG. 2C.